package lhc.alg.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * description: https://leetcode.cn/problems/valid-parenthesis-string/
 *  栈 求解，可用贪心
 * author: hongchen.liao
 * date:  2022/8/22
 */
public class _678_Valid_Parenthesis_String {

    class Solution {
        public boolean checkValidString(String s) {
            Deque<Integer> leftStack = new LinkedList<>();
            Deque<Integer> asterisSatck = new LinkedList<>();
            int n = s.length();
            for(int i = 0; i < n; i++){
                char ch = s.charAt(i);
                if(ch == '('){
                    leftStack.push(i);
                }else if( ch == '*'){
                    asterisSatck.push(i);
                }else{
                    if(!leftStack.isEmpty()){
                        leftStack.pop();
                    }else if(!asterisSatck.isEmpty()){
                        asterisSatck.pop();
                    }else{
                        return false;
                    }
                }
            }
            while(!leftStack.isEmpty() && !asterisSatck.isEmpty()){
                int leftIndex = leftStack.pop();
                int asterisIndex = asterisSatck.pop();
                if(leftIndex > asterisIndex){
                    return false;
                }
            }
            return leftStack.isEmpty();
        }
    }

}
